|
Grover's algorithm is a quantum algorithm that finds with high probability the unique input to a black box function that produces a particular output value, using just evaluations of the function, where is the size of the function's domain. The analogous problem in classical computation cannot be solved in fewer than evaluations (because, in the worst case, the Nth member of the domain might be the correct member). At roughly the same time that Grover published his algorithm, Bennett, Bernstein, Brassard, and Vazirani published a proof that no quantum solution to the problem can evaluate the function fewer than times, so Grover's algorithm is asymptotically optimal.〔Bennett C.H., Bernstein E., Brassard G., Vazirani U., ''(The strengths and weaknesses of quantum computation )''. SIAM Journal on Computing 26(5): 1510–1523 (1997). Shows the optimality of Grover's algorithm.〕 Unlike other quantum algorithms, which may provide exponential speedup over their classical counterparts, Grover's algorithm provides only a quadratic speedup. However, even quadratic speedup is considerable when is large. Grover's algorithm could brute force a 128-bit symmetric cryptographic key in roughly 264 iterations, or a 256-bit key in roughly 2128 iterations. As a result, it is sometimes suggested that symmetric key lengths be doubled to protect against future quantum attacks. Like many quantum algorithms, Grover's algorithm is probabilistic in the sense that it gives the correct answer with a probability of less than 1. Though there is technically no upper bound on the number of repetitions that might be needed before the correct answer is obtained, the expected number of repetitions is a constant factor that does not grow with . Grover's original paper described the algorithm as a database search algorithm, and this description is still common. The database in this analogy is a table of all of the function's outputs, indexed by the corresponding input. == Applications == Although the purpose of Grover's algorithm is usually described as "searching a database", it may be more accurate to describe it as "inverting a function". Roughly speaking, if we have a function ''y = f(x)'' that can be evaluated on a quantum computer, Grover's algorithm allows us to calculate ''x'' when given ''y''. Inverting a function is related to the searching of a database because we could come up with a function that produces one particular value of ''y'' ("true" for instance) if ''x'' matches a desired entry in a database, and another value of ''y'' ("false") for other values of ''x''. Grover's algorithm can also be used for estimating the mean and median of a set of numbers, and for solving the Collision problem. The algorithm can be further optimized if there is more than one matching entry and the number of matches is known beforehand. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Grover's algorithm」の詳細全文を読む スポンサード リンク
|